home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / GRAPHICS / VOXRAY.ZIP / BSPCONV.C < prev    next >
Encoding:
C/C++ Source or Header  |  1995-10-25  |  14.2 KB  |  546 lines
  1. /* bspstruc.c */
  2. #include "ray.h"
  3. #include "globals.h"
  4. #include "idbsp.h"
  5. #include "sortseg.h"
  6. #include <mem.h>
  7.                           
  8. #define Get_Sec_From_SSec(x) ((Seg_List+((x)->seg_start))->ld->s[(short)(Seg_List+((x)->seg_start))->left_sidedef]->sec)
  9.  
  10.                           
  11. /*
  12. id              secstore_i;
  13. id              mapvertexstore_i;
  14. id              subsecstore_i;
  15. id              maplinestore_i;
  16. id              nodestore_i;
  17. id              mapthingstore_i;
  18. id              ldefstore_i;
  19. id              sdefstore_i;
  20. */
  21.  
  22. STORAGE *subsecstore_i;
  23. STORAGE *maplinestore_i;
  24. STORAGE *nodestore_i;
  25.  
  26. void * MyRealloc(void * ptr, long old_size, long new_size) {
  27.     void * temp_ptr=SafeMalloc(new_size);
  28.     memmove(temp_ptr, ptr, old_size);
  29.     Free_Mem(ptr);
  30.     return temp_ptr;
  31. }
  32.  
  33. /*
  34. ===============================================================================
  35.  
  36.                             PROCESSING
  37.  
  38. ===============================================================================
  39. */
  40.  
  41. /*
  42. =================
  43. =
  44. = LineFromSeg
  45. =
  46. =================
  47. */
  48.  
  49. void LineFromSeg(mapseg_t * seg, line_t * line) {
  50. memset(line, 0, sizeof(line));
  51. line->p1.x=Vector_List[seg->v1].x;
  52. line->p1.y=Vector_List[seg->v1].y;
  53. line->p2.x=Vector_List[seg->v2].x;
  54. line->p2.y=Vector_List[seg->v2].y;
  55. }
  56.  
  57. /*
  58. =================
  59. =
  60. = UniqueVertex
  61. =
  62. = Returns the vertex number, adding a new vertex if needed
  63. =================
  64. */
  65.  
  66. int UniqueVertex (int x, int y)
  67. {
  68.     int                             i, count;
  69.     vector2             mv;
  70.     pvector2 mvp;
  71.  
  72.     mv.x = x;
  73.     mv.y = y;
  74.  
  75. /* see if an identical vertex already exists */
  76. /*
  77.     count = [mapvertexstore_i count];
  78.     mvp = [mapvertexstore_i elementAt:0];
  79. */
  80.     count = Number_Of_Vectors;
  81.     mvp=Vector_List;
  82.     for (i=0 ; i<count ; i++, mvp++)
  83.         if (mvp->x == mv.x && mvp->y == mv.y)
  84.             return i;
  85.  
  86. /*      [mapvertexstore_i addElement: &mv]; */
  87.     Number_Of_Vectors++;
  88.     Vector_List = (pvector2)MyRealloc(Vector_List,
  89.     sizeof(vector2) * (Number_Of_Vectors-1),
  90.           sizeof(vector2) * (Number_Of_Vectors));
  91.     memcpy(Vector_List+Number_Of_Vectors-1, &mv,                         
  92.                     sizeof(vector2));
  93.  
  94.  
  95.     return count;
  96. }
  97.  
  98.  
  99. /*
  100. =============================================================================
  101. */
  102.  
  103. float   bbox[4];
  104.  
  105. /*
  106. =================
  107. =
  108. = AddPointToBBox
  109. =
  110. =================
  111. */
  112.  
  113. void AddPointToBBox (float x, float y)
  114. {
  115.     if (x < bbox[BOXLEFT])
  116.         bbox[BOXLEFT] = x;
  117.     if (x > bbox[BOXRIGHT])
  118.         bbox[BOXRIGHT] = x;
  119.  
  120.     if (y > bbox[BOXTOP])
  121.         bbox[BOXTOP] = y;
  122.     if (y < bbox[BOXBOTTOM])
  123.         bbox[BOXBOTTOM] = y;
  124. }
  125.  
  126.  
  127. /*
  128. =================
  129. =
  130. = ProcessLines
  131. =
  132. = Adds the lines in a subsector to the mapline storage
  133. =================
  134. */
  135.  
  136. /* void ProcessLines (id store_i) */
  137. void ProcessLines(STORAGE *store_i)
  138. {
  139.     int                     i,count;
  140.     line_t          *wline;
  141.     mapseg_t        line;
  142.     short           angle;
  143.     float           fangle;
  144.  
  145.     bbox[BOXLEFT] = INT_MAX;
  146.     bbox[BOXRIGHT] = INT_MIN;
  147.     bbox[BOXTOP] = INT_MIN;
  148.     bbox[BOXBOTTOM] = INT_MAX;
  149.  
  150. /*      count = [store_i count]; */
  151.     count = store_i->count;
  152.     for (i=0 ; i<count ; i++)
  153.     {
  154. /*              wline = [store_i elementAt: i]; */
  155.         wline = (line_t *)store_i->data + i;
  156.         if (wline->grouped)
  157.             printf ("ERROR: line regrouped\n");
  158.         wline->grouped = true;
  159.  
  160.         memset (&line, 0, sizeof(line));
  161.         AddPointToBBox (wline->p1.x, wline->p1.y);
  162.         AddPointToBBox (wline->p2.x, wline->p2.y);
  163.         line.v1 = UniqueVertex (wline->p1.x, wline->p1.y);
  164.         line.v2 = UniqueVertex (wline->p2.x, wline->p2.y);
  165.         line.linedef = wline->linedef;
  166.         line.side = wline->side;
  167.         line.offset = wline->offset;
  168.         fangle = atan2 (wline->p2.y - wline->p1.y, wline->p2.x - wline->p1.x);
  169. /************************ CHANGED BY MATT! *********************************/                
  170.         angle = (short)(fangle/(PI*2)*ANGLE_360);
  171.         if (angle<0) angle+=ANGLE_360; // get rid of negative angles
  172. /************************ END CHANGED BY MATT! *****************************/
  173.         line.angle = angle;
  174. /*              [maplinestore_i addElement: &line]; */
  175.         memcpy((mapseg_t *)maplinestore_i->data + maplinestore_i->count, &line,
  176.                         sizeof(line));
  177.         maplinestore_i->count += 1;
  178.         maplinestore_i->data = (mapseg_t *)MyRealloc(maplinestore_i->data,
  179.             sizeof(mapseg_t) * (maplinestore_i->count),
  180.                          sizeof(mapseg_t) * (maplinestore_i->count+1));
  181.     }
  182. }
  183.  
  184. /*
  185. =================
  186. =
  187. = FinishCut
  188. =
  189. = Cuts a box agains lines in sub sector ****MADE BY MATT****
  190. =================
  191. */
  192.  
  193. STORAGE * FinishCut(mapsubsector_t * cur_ssec, STORAGE * cutbox_i)
  194. {
  195. STORAGE * new_front;
  196. STORAGE * back_temp;
  197. STORAGE * cur_list;
  198. short cur_seg_index;             
  199. mapseg_t * cur_seg;
  200. line_t spliton;
  201. cur_list=cutbox_i;
  202.  
  203. for (cur_seg_index=0; cur_seg_index<cur_ssec->numsegs; cur_seg_index++) {
  204.     cur_seg=(mapseg_t *)maplinestore_i->data+cur_ssec->firstseg+cur_seg_index;        
  205.     LineFromSeg(cur_seg, &spliton); 
  206.     
  207.     new_front=(STORAGE *)SafeMalloc(sizeof(STORAGE));
  208.     new_front->count = 0;
  209.     new_front->size = sizeof(vector2);
  210.     new_front->data = (pvector2)SafeMalloc(sizeof(vector2));
  211.  
  212.     back_temp=(STORAGE *)SafeMalloc(sizeof(STORAGE));
  213.     back_temp->count = 0;
  214.     back_temp->size = sizeof(vector2);
  215.     back_temp->data = (pvector2)SafeMalloc(sizeof(vector2));
  216.  
  217.     SplitCutBoxes(cur_list, &spliton, new_front, back_temp);
  218.     
  219.     Free_Mem(back_temp->data);
  220.     Free_Mem(back_temp);
  221.     Free_Mem(cur_list->data);
  222.     Free_Mem(cur_list);
  223.  
  224.     cur_list=new_front;
  225. }
  226. return cur_list;
  227. }
  228.  
  229. /*
  230. =================
  231. =
  232. = Makes alternate bound box, using cut box
  233. =
  234. =================
  235. */
  236.  
  237. void Make_Alt_BBox(mapsubsector_t * cur_ssec) {
  238.     pvector2 cur_vec;
  239.     short count, counter;
  240.  
  241.     bbox[BOXLEFT] = INT_MAX;
  242.     bbox[BOXRIGHT] = INT_MIN;
  243.     bbox[BOXTOP] = INT_MIN;
  244.     bbox[BOXBOTTOM] = INT_MAX;
  245.  
  246.   count=cur_ssec->cutbox->count;
  247.   for (counter=0; counter<count; counter++) {
  248.       cur_vec=(pvector2)cur_ssec->cutbox->data+counter;
  249.       AddPointToBBox(cur_vec->x, cur_vec->y);
  250.     }
  251. }
  252.  
  253. /*         
  254. =================
  255. =
  256. = ProcessSubsector
  257. =
  258. =================
  259. */
  260.  
  261. /* int ProcessSubsector (id wmaplinestore_i) */
  262. int ProcessSubsector(STORAGE *wmaplinestore_i, STORAGE *cutbox_i)
  263. {
  264.     int                             count;
  265.     worldline_t             *linedef;
  266.     line_t                  *wline;
  267.     mapsubsector_t  sub;
  268.  
  269.     memset (&sub,0,sizeof(sub));
  270.  
  271. /*      count = [wmaplinestore_i count]; */
  272.     count = wmaplinestore_i->count;
  273.     if (count < 1)
  274.         Error ("ProcessSubsector: count = %i",count);
  275.  
  276. /*      wline = [wmaplinestore_i elementAt: 0]; */
  277.     wline = wmaplinestore_i->data;
  278.  
  279. /*      linedef = [linestore_i elementAt: wline->linedef]; */
  280.     linedef = (worldline_t *)linestore_i->data + wline->linedef;
  281.                 sub.numsegs = count;
  282. /*      sub.firstseg = [maplinestore_i count]; */
  283.                 sub.firstseg = maplinestore_i->count;
  284.                 ProcessLines (wmaplinestore_i);
  285.  
  286.     sub.cutbox=FinishCut(&sub, cutbox_i); 
  287.           Make_Alt_BBox(&sub);
  288.  
  289.     
  290. /* add the new subsector
  291.                 [subsecstore_i addElement: &sub];
  292. */
  293.                 memcpy((mapsubsector_t *)subsecstore_i->data + subsecstore_i->count, &sub,
  294.                                                                                 sizeof(mapsubsector_t));
  295.                 subsecstore_i->count += 1;
  296.                 subsecstore_i->data = (mapsubsector_t *)MyRealloc(subsecstore_i->data,
  297.                                               sizeof(mapsubsector_t) * (subsecstore_i->count),
  298.                                         sizeof(mapsubsector_t) * (subsecstore_i->count + 1));
  299.  
  300. /*      return [subsecstore_i count]-1; */
  301.                 return subsecstore_i->count - 1;
  302. }
  303.  
  304. /*
  305. =================
  306. =
  307. = ProcessNode
  308. =
  309. =================
  310. */
  311.  
  312. int ProcessNode (bspnode_t *node, short *totalbox)
  313. {
  314.     short           subbox[2][4];
  315.     int                     i, r;
  316.     mapnode_t       mnode;
  317.  
  318.     memset (&mnode,0,sizeof(mnode));
  319.  
  320.     if (node->lines_i)      /* NF_SUBSECTOR flags a subsector */
  321.     {
  322.         r = ProcessSubsector (node->lines_i, node->cutbox_i);
  323.         for (i=0 ; i<4 ; i++)
  324.             totalbox[i] = bbox[i];
  325.         return r | NF_SUBSECTOR;
  326.     }
  327.  
  328.     mnode.x =node->divline.pt.x;
  329.     mnode.y =node->divline.pt.y;
  330.     mnode.dx =node->divline.dx;
  331.     mnode.dy =node->divline.dy;
  332.  
  333.     r = ProcessNode(node->side[0], subbox[0]);
  334.     mnode.children[0] =r;
  335.     for (i=0 ; i<4 ; i++)
  336.         mnode.bbox[0][i] =subbox[0][i];
  337.  
  338.     r = ProcessNode (node->side[1],subbox[1]);
  339.     mnode.children[1] =r;
  340.     for (i=0 ; i<4 ; i++)
  341.         mnode.bbox[1][i] =subbox[1][i];
  342.  
  343.     totalbox[BOXLEFT] = MIN(subbox[0][BOXLEFT], subbox[1][BOXLEFT]);
  344.     totalbox[BOXTOP] = MAX(subbox[0][BOXTOP], subbox[1][BOXTOP]);
  345.     totalbox[BOXRIGHT] = MAX(subbox[0][BOXRIGHT], subbox[1][BOXRIGHT]);
  346.     totalbox[BOXBOTTOM] = MIN(subbox[0][BOXBOTTOM], subbox[1][BOXBOTTOM]);
  347.  
  348. /*      [nodestore_i addElement: &mnode]; */
  349.     memcpy((mapnode_t *)nodestore_i->data + nodestore_i->count, &mnode, sizeof(mapnode_t));
  350.     nodestore_i->count += 1;
  351.     nodestore_i->data = (mapnode_t *)MyRealloc(nodestore_i->data,
  352.               sizeof(mapnode_t) * (nodestore_i->count),
  353.                                             sizeof(mapnode_t) * (nodestore_i->count + 1));
  354.  
  355. /*      return [nodestore_i count] - 1; */
  356.     return nodestore_i->count - 1;
  357. }
  358.  
  359.  
  360. /*
  361. =================
  362. =
  363. = ProcessNodes
  364. =
  365. = Recursively builds the nodes, subsectors, and line lists,
  366. = then writes the lumps
  367. =================
  368. */
  369.  
  370. void ProcessNodes (void)
  371. {
  372.     short   worldbounds[4];
  373. /*
  374.     subsecstore_i = [[Storage alloc]
  375.         initCount:              0
  376.         elementSize:    sizeof(mapsubsector_t)
  377.         description:    NULL];
  378.     maplinestore_i = [[Storage alloc]
  379.         initCount:              0
  380.         elementSize:    sizeof(mapseg_t)
  381.         description:    NULL];
  382.     nodestore_i = [[Storage alloc]
  383.         initCount:              0
  384.         elementSize:    sizeof(mapnode_t)
  385.         description:    NULL];
  386. */
  387.     subsecstore_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
  388.     subsecstore_i->data = (mapsubsector_t *)SafeMalloc(sizeof(mapsubsector_t));
  389.     subsecstore_i->count = 0;
  390.     subsecstore_i->size = sizeof(mapsubsector_t);
  391.  
  392.     maplinestore_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
  393.     maplinestore_i->data = (mapseg_t *)SafeMalloc(sizeof(mapseg_t));
  394.     maplinestore_i->count = 0;
  395.     maplinestore_i->size = sizeof(mapseg_t);
  396.  
  397.     nodestore_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
  398.     nodestore_i->data = (mapnode_t *)SafeMalloc(sizeof(mapnode_t));
  399.     nodestore_i->count = 0;
  400.     nodestore_i->size = sizeof(mapnode_t);
  401.  
  402.     ProcessNode (startnode, worldbounds);
  403.  
  404. }
  405.  
  406. /*
  407. =============================================================================
  408. */
  409.  
  410. /*
  411. ==================
  412. =
  413. = ConvertNodes
  414. =
  415. = Converts data to My format ****MADE BY MATT****
  416. ==================
  417. */
  418.  
  419. void ConvertNodes() {
  420. short counter;
  421. pseg cur_seg;
  422. pssector cur_ssec;
  423. bsp_node * cur_node;
  424. prectl cur_rect;
  425. mapseg_t * cur_doom_seg;
  426. mapsubsector_t * cur_doom_ssec;
  427. mapnode_t * cur_doom_node;
  428. psorted_vector_type sorted_list;
  429.  
  430. // Seg conversion
  431. Number_Of_Segs=maplinestore_i->count;
  432. Seg_List=(pseg)SafeMalloc(Number_Of_Segs * sizeof(seg));
  433. for (counter=0; counter<Number_Of_Segs; counter++) {
  434.     cur_seg=Seg_List+counter;
  435.     cur_doom_seg=(mapseg_t *)maplinestore_i->data+counter;
  436.     cur_seg->v[0]=cur_doom_seg->v1;
  437.     cur_seg->v[1]=cur_doom_seg->v2;
  438.     cur_seg->angle=cur_doom_seg->angle;
  439.     cur_seg->ld=Ld_List+cur_doom_seg->linedef;
  440.     cur_seg->left_sidedef=(cur_doom_seg->side > 0 ? TRUE : FALSE);
  441.     cur_seg->linedef_offset=cur_doom_seg->offset;
  442. }
  443. Free_Mem(maplinestore_i->data);
  444. Free_Mem(maplinestore_i);
  445.  
  446. // SubSector conversion
  447. Number_Of_SSectors=subsecstore_i->count;
  448. SS_List=(pssector)SafeMalloc(Number_Of_SSectors * sizeof(ssector));
  449. for (counter=0; counter<Number_Of_SSectors; counter++) {
  450.     cur_ssec=SS_List+counter;
  451.     cur_doom_ssec=(mapsubsector_t *)subsecstore_i->data+counter;
  452.     cur_ssec->seg_start=cur_doom_ssec->firstseg;
  453.     cur_ssec->seg_end=cur_doom_ssec->firstseg+cur_doom_ssec->numsegs-1;
  454.     cur_ssec->flags=Get_Sec_From_SSec(cur_ssec)->flags;
  455.     if (cur_ssec->flags & VOXEL_SSECTOR) {
  456.         sorted_list=(psorted_vector_type)SafeMalloc(sizeof(sorted_vector_type));
  457.         sorted_list->vector_count=cur_doom_ssec->cutbox->count;
  458.         sorted_list->vectors=cur_doom_ssec->cutbox->data;
  459.         cur_ssec->extra_data=(pdata)sorted_list;
  460.     } else { 
  461.         Free_Mem(cur_doom_ssec->cutbox->data);
  462.         Free_Mem(cur_doom_ssec->cutbox);
  463.         cur_ssec->extra_data=NULL;
  464.     }
  465.     cur_ssec->objects=NULL;
  466.     cur_ssec->num_objects=0;                  
  467. }
  468. Free_Mem(subsecstore_i->data);
  469. Free_Mem(subsecstore_i);
  470.  
  471. // Node conversion
  472. Number_Of_Nodes=nodestore_i->count;
  473. bsp_start_node=nodestore_i->count-1;
  474. bsp_tree=(bsp_node *)SafeMalloc(Number_Of_Nodes * sizeof(bsp_node));
  475. for (counter=0; counter<Number_Of_Nodes; counter++) {
  476.     cur_node=bsp_tree+counter;
  477.     cur_doom_node=(mapnode_t *)nodestore_i->data+counter;
  478.     cur_node->x1=cur_doom_node->x;
  479.     cur_node->y1=cur_doom_node->y;
  480.     cur_node->x2=cur_doom_node->x+cur_doom_node->dx;
  481.     cur_node->y2=cur_doom_node->y+cur_doom_node->dy;
  482.     cur_rect=&(cur_node->left_bound);
  483.     cur_rect->top=cur_doom_node->bbox[1][BOXTOP];
  484.     cur_rect->left=cur_doom_node->bbox[1][BOXLEFT];
  485.     cur_rect->bottom=cur_doom_node->bbox[1][BOXBOTTOM];
  486.     cur_rect->right=cur_doom_node->bbox[1][BOXRIGHT];
  487.     cur_rect=&(cur_node->right_bound);
  488.     cur_rect->top=cur_doom_node->bbox[0][BOXTOP];
  489.     cur_rect->left=cur_doom_node->bbox[0][BOXLEFT];
  490.     cur_rect->bottom=cur_doom_node->bbox[0][BOXBOTTOM];
  491.     cur_rect->right=cur_doom_node->bbox[0][BOXRIGHT];
  492.     cur_node->left_child=cur_doom_node->children[1];
  493.     cur_node->right_child=cur_doom_node->children[0];
  494. } /* endfor */
  495. Free_Mem(nodestore_i->data);
  496. Free_Mem(nodestore_i);
  497.  
  498. }
  499.  
  500. /*
  501. ==================
  502. =
  503. = Make_Line_List
  504. =
  505. = Makes linedefs usable by bsp generator ****MADE BY MATT*****
  506. ==================
  507. */
  508.  
  509. void Make_Line_List() {
  510.     short counter;
  511.     plinedef cur_ld;
  512.     worldline_t * cur_doom_ld;
  513.  
  514.     linestore_i=(STORAGE *)SafeMalloc(sizeof(STORAGE));
  515.     linestore_i->count=Number_Of_Linedefs;
  516.     linestore_i->size=Number_Of_Linedefs * sizeof(worldline_t);
  517.     linestore_i->data=(worldline_t *)SafeMalloc(linestore_i->size);
  518.  
  519.     for (counter=0; counter<Number_Of_Linedefs; counter++) {
  520.         cur_ld=Ld_List+counter;
  521.         cur_doom_ld=(worldline_t *)linestore_i->data+counter;
  522.         cur_doom_ld->p1.x=Vector_List[cur_ld->v[0]].x;
  523.         cur_doom_ld->p1.y=Vector_List[cur_ld->v[0]].y;
  524.         cur_doom_ld->p2.x=Vector_List[cur_ld->v[1]].x;
  525.         cur_doom_ld->p2.y=Vector_List[cur_ld->v[1]].y;
  526.         cur_doom_ld->tag=cur_ld->tag;
  527.         cur_doom_ld->special=cur_ld->tag_type;
  528.         cur_doom_ld->flags=cur_ld->attributes;
  529.     }
  530. }
  531.  
  532. /*                                      
  533. ==================
  534. =
  535. = ConvBSP
  536. =
  537. ==================
  538. */
  539.  
  540. void ConvBSP (void)
  541. {
  542.     ProcessNodes ();
  543.     ConvertNodes();
  544. }
  545.  
  546.